package com.zbl.小题大做;

public class 二叉树 {
    /*
    宽度优先遍历，二叉树每层数据转成转成二维数组
    1、二叉树头节点放入fifo队列
    2、记录节点数size，即为查找层的所有父节点数
    3、把每个节点的子节点放入此队列，size - 1
    4、size为0表示当前层查找完毕，组成一个数组添加进ans
    5、继续2、3、4，直到fifo为空
    
     */

    /**
     * 先序遍历，头、左、右
     * 中序遍历，左，头，右
     * 后序遍历，左、右、头
     */

    /*

    根据先序遍历数组和中序遍历数组，构成树
    原二叉树无重复值
     
    解题方案：
    1、先序能确定头节点，在中序中拿到头节点能确定左右树的节点有哪些，继而确定先序的左右树节点存放位置
    2、先序的左树和中序的左树根据1继续递归划分，当先序等于中序时，即size=1时，划分已然接近尾声，所以结束的判断是size > 0
    3、返回最开始的头节点
    补充：减少中间变量产生和重复遍历，递归方法参数（原先序，先序左边界，先序右边界，原中序，中序左边界，中序右边界，中序map<节点，下标>）
     */

    /**
     * 完全二叉树，节点从上到下，从左到右，依次排布，叶子节点在最后一层，满二叉树：最后一层叶子节点为满的
     */

    /*
    2023金三突击 - 12 - 01:25
    判断是否是完全二叉树
    解题方案：
    一、宽度优先遍历，1、没有左节点，不能有右节点；2、没有子节点或只有左子节点，后续遍历节点不能有子节点 
    二、先序递归遍历，1、没有左节点，不能有右节点；2、没有子节点或只有左子节点，记录此时深度size，后续遍历节点深度小于size的需要同时有左右子节点，深度等于size时不能有子节点
     */

    /**
     * 搜索二叉树，
     * 1、左子树所有节点值小于根节点
     * 2、右子树所有节点值大于根节点
     * 3、左右子树都是二叉搜索树
     */

    /*
    2023金三突击 - 12 - 01:45
    搜索二叉树判断 
     */

    /**
     * 平衡二叉树
     * 1、左右子树深度差不超过1
     */
    /*
    2023金三突击 - 12 - 01:52
    搜索二叉树判断 
     */
}
